#!/usr/bin/env python
import heapq
import math
import sys

import search

sys.setrecursionlimit(100000)

inicial = [7, 2, 4, 5, 0, 6, 8, 3, 1]
objetivo = [0, 1, 2, 3, 4, 5, 6, 7, 8]

def h(jogo):
    l = jogo.tabuleiro
    size = int(math.sqrt(len(l)))
    result = 0
    for i, a in enumerate(l):
        lin1, col1 = i / size, i % size
        target = objetivo.index(a)
        lin2, col2 = target / size, target % size
        result += abs(lin1 - lin2) + abs(col1 - col2)
    return result

class Jogo(search.Try):
    def __init__(self):
        self.tabuleiro = inicial
    def is_solution(self):
        return self.tabuleiro == objetivo
        
    def copy(self):
        novo_jogo = Jogo()
        novo_jogo.tabuleiro = list(self.tabuleiro)
        return novo_jogo

    def _move(self, rel_lin, rel_col):
        index = self.tabuleiro.index(0)
        size = int(math.sqrt(len(self.tabuleiro)))
        lin1, col1 = index / size, index % size
        lin2, col2 = lin1 + rel_lin, col1 + rel_col
        if lin2 < 0 or col2 < 0 or \
           lin2 >= size or col2 >= size:
            return self
        size = int(math.sqrt(len(self.tabuleiro)))
        pos1 = lin1 * size + col1
        pos2 = lin2 * size + col2
        self.tabuleiro[pos1], self.tabuleiro[pos2] = self.tabuleiro[pos2], self.tabuleiro[pos1]
        return self

    def move_cima(self): return self._move(-1, 0)
    def move_baixo(self): return self._move(1, 0)
    def move_esquerda(self): return self._move(0, -1)
    def move_direita(self): return self._move(0, 1)
        
    def __eq__(self, other):
        return self.tabuleiro == other.tabuleiro

    def __hash__(self):
        return hash(':'.join([ str(x) for x in self.tabuleiro]))
    
    def __repr__(self):
        return str(self.tabuleiro)

def main():
    rules = [ Jogo.move_cima, Jogo.move_baixo, \
              Jogo.move_esquerda, Jogo.move_direita ]
    print 'A*'
    for l in search.astar_search(Jogo, rules, h):
        print l
    print 'GULOSA'
    for l in search.gulosa_search(Jogo, rules, h):
        print l
    print 'PROFUNDIDADE'
    for l in search.depth_search(Jogo, rules):
        print l
    print 'LARGURA'
    for l in search.breadth_search(Jogo, rules):
        print l

if __name__ == '__main__':
    main()
